package main

//#link:https://leetcode-cn.com/problems/house-robber-ii/
func main() {

}

//相比于打家劫舍版本1多了一个环
//在打家劫舍的基础上，若选择了第一个则不能选择最后一个，若选择了最后一个则不能选择第一个，所以可以分为两段，选择第一个[0:len(nums)-1],选择最后一个[1:]，两者取最大值即可
func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	return max(getMax(nums[0:len(nums)-1]), getMax(nums[1:]))
}

func getMax(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-1], dp[i-2]+nums[i])
	}
	return dp[len(nums)-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
